import java.util.Arrays;

/**
 * 二叉堆的实现
 */
public class BinaryHeap {


    public static void main(String[] args) {
        int[] array = {7, 1, 3, 5, 6, 4, 2, 8, 9};
        sort(array);
        System.out.println(Arrays.toString(array));
    }

    /**
     * 堆排序
     * 先将无序数组转换为二叉堆
     * 再将每个堆顶元素进行一次下沉
     *
     * @param array
     */
    public static void sort(int[] array) {
        /**
         * 将无序数组调整成二叉堆
         */
        buildBinaryHeap(array);

        for (int i = array.length - 1; i > 0; i--) {
            //删除对顶、放置到堆尾部、实则交换元素
            int temp = array[0];
            array[0] = array[i];
            array[i] = temp;
            //将堆顶部元素进行下沉
            sinking(array, 0, i);
        }
    }


    public static void buildBinaryHeap(int[] array) {
        //除去叶子节点、将每个节点进行下沉操作
        for (int i = (array.length - 2) / 2; i >= 0; i--) {
            sinking(array, i, array.length - 1);
        }
    }

    /**
     * 构建二叉堆、让当前元素下沉
     *
     * @param array     被操作的数组
     * @param itemIndex 当前元素下标
     * @param length    当前二叉堆长度
     */
    public static void sinking(int[] array, int itemIndex, int length) {
        //父节点值
        int parent = array[itemIndex];

        //默认操作的是左孩子
        int childIndex = 2 * itemIndex + 1;

        while (childIndex < length) {

            //存在右边子元素、并且右边子元素值小于左边
            if (childIndex + 1 < length && array[childIndex + 1] < array[childIndex]) {
                //切换到右边元素
                childIndex++;
            }

            //小于等于则无需交换
            if (parent <= array[childIndex]) break;

            //无需交换、只需要将子元素移动到父元素位置即可
            array[itemIndex] = array[childIndex];
            itemIndex = childIndex;

            //改变左右子元素的下标
            childIndex = 2 * itemIndex + 1;
        }
        //最终将父元素移动到指定位置即可。
        array[itemIndex] = parent;
    }


}
